import copy

class Coord:
    def __init__(self, r, c):
        self.r = r
        self.c = c
    
    def __hash__(self):
        return (self.r+self.c)*(self.r+self.c+1)//2+self.c
    
    def __eq__(self, other):
        return self.r==other.r and self.c==other.c
    
    def __ne__(self, other):
        return self.r!=other.r or self.c!=other.c

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        cDict = {}
        for word in words:
            d = cDict
            for i in range(len(word)):
                c = word[i]
                if c not in d:
                    d.update({c:{}})
                d = d[c]
                if i==len(word)-1:
                    d.update({"end":None})
        
        nRow = len(board)
        nCol = len(board[0])

        ret = []

        def remove(path, d):
            if len(path)==0:
                del d["end"]
                return
            ch = path[0]
            remove(path[1:], d[ch])
            if len(d[ch])==0:
                del d[ch]

        def find(r, c, acc, track, d):
            if "end" in d:
                ret.append("".join(acc))
                remove(acc, cDict)

            # up
            if r-1>=0:
                ch = board[r-1][c]
                coord = Coord(r-1,c)
                if ch in d and coord not in track:
                    acc.append(ch)
                    track.add(coord)
                    find(r-1, c, acc, track, d[ch])
                    track.remove(coord)
                    acc.pop()
            # right
            if c+1<nCol:
                ch = board[r][c+1]
                coord = Coord(r,c+1)
                if ch in d and coord not in track:
                    acc.append(ch)
                    track.add(coord)
                    find(r, c+1, acc, track, d[ch])
                    track.remove(coord)
                    acc.pop()
            # down
            if r+1<nRow:
                ch = board[r+1][c]
                coord = Coord(r+1,c)                
                if ch in d and coord not in track:
                    acc.append(ch)
                    track.add(coord)
                    find(r+1, c, acc, track, d[ch])
                    track.remove(coord)
                    acc.pop()
            # left
            if c-1>=0:
                ch = board[r][c-1]
                coord = Coord(r,c-1)
                if ch in d and coord not in track:
                    acc.append(ch)
                    track.add(coord)
                    find(r, c-1, acc, track, d[ch])
                    track.remove(coord)
                    acc.pop()
            
        for r in range(nRow):
            for c in range(nCol):
                ch = board[r][c]
                if ch in cDict:
                    track = set([Coord(r, c)])
                    find(r, c, [ch], track, cDict[ch])
        
        return ret

print(Solution().findWords(["ab","cd"],
["ab","cb","ad","bd","ac","ca","da","bc","db","adcb","dabc","abb","acb"]))